class Solution {
public:
    int minCut(string s) {
        vector<vector<int> > dp1(s.size(),vector<int>(s.size(),0));
        vector<int> dp2(s.size(),0);
        int ret = -1;
        for(int i = s.size() - 1;i >= 0;i--){
            dp2[i] = i;
            for(int j = i;j < s.size();j++){
                if(s[i] == s[j]){
                    if(j - i <= 2 || dp1[i+1][j-1] == 1){
                        dp1[i][j] = 1;
                    }
                }
            }
        }
        for(int i = 1;i < s.size();i++){
            if(dp1[0][i]){
                dp2[i] = 0;
                continue;
            }
            for(int j = 1;j <= i;j++){
                if(dp1[j][i]){
                    dp2[i] = min(dp2[j-1]+1,dp2[i]);
                }
            }
        }
        return dp2[s.size() - 1];
    }
};
